﻿
namespace Graph.Algorithm.Core
{
    /// <summary>
    /// 退火算法
    /// </summary>
    public class AnnealService
    {
        double temperature = 10E6;
        double decay = 0.0001;

        public int[] path { get; set; }

        public List<int> bestPath = new List<int>();

        public static Random randomBuilder = new Random();
        public static MatrixBuilder<double> matBuilder { get; set; } = Matrix<double>.Build;

        static Matrix<double> matrixDistance;

        public AnnealService(IEnumerable<GraphEdge> edges)
        {
            var groups = edges.GroupBy(e => e.stVertexId);
            var cityNum = groups.Count();
            matrixDistance = matBuilder.Dense(cityNum, cityNum);

            for (int i = 0; i < cityNum; i++)
            {
                for (int j = 0; j < cityNum; j++)
                {
                    matrixDistance[i, j] = i == j ? 0 : edges.At(i, j).weight;
                }
            }

            path = new int[cityNum];
            for (int i = 0; i < cityNum; i++)
            {
                path[i] = i;
            }
            bestPath = path.ToList();
        }
        public AnnealService(Matrix<double> _matrixDistance)
        {
            matrixDistance = _matrixDistance;
            int cityNum = _matrixDistance.RowCount;
              
            path = new int[cityNum];
            for (int i = 0; i < cityNum; i++)
            {
                path[i] = i;
            }
            bestPath = path.ToList();
        }


        public void RunAlgm(int numberOfGeneration)
        {
            var curPath = path;

            while (numberOfGeneration > 0 || temperature > 1)
            {
                numberOfGeneration--;
                temperature = temperature * (1 - decay);


                var curDist = PathLength(curPath);
                var newPath = SwitchRandom(curPath);
                var newDist = PathLength(newPath);

                var judge = JudgeFunc(curDist, newDist);

                var threshold = randomBuilder.Next(100) * 0.01;
                if (judge > threshold)
                {
                    curPath = newPath;
                }
            }

            bestPath = curPath.ToList();
        }

        /// <summary>
        /// 评价函数
        /// </summary>
        /// <param name="curDist"></param>
        /// <param name="newDist"></param>
        /// <returns></returns>
        public double JudgeFunc(double curDist, double newDist)
        {
            var deltaDist = newDist - curDist;

            if (deltaDist < 0)
            {
                return 1;
            }
            else
            {
                var tmpp = 1 / Math.Exp(deltaDist / temperature);
                return tmpp;
            }
        }


        /// <summary>
        /// 计算当前路径的总路程
        /// </summary>
        /// <param name="_paths"></param>
        /// <returns></returns>
        public static double PathLength(int[] _paths)
        {
            double pathSum = 0;
            for (int i = 0; i < _paths.Length - 1; i++)
            {
                pathSum += matrixDistance[_paths[i], _paths[i + 1]];
            }
            return pathSum;
        }


        /// <summary>
        /// 随机互换
        /// </summary>
        /// <param name="_paths"></param>
        /// <returns></returns>
        public int[] SwitchRandom(int[] _paths)
        {
            var index1 = randomBuilder.Next(0, _paths.Count());
            var index2 = randomBuilder.Next(0, _paths.Count());
            while (index1 == index2)
            {
                index2 = randomBuilder.Next(0, _paths.Count());
            }

            int tmp1 = _paths[index1];
            int tmp2 = _paths[index2];

            _paths[index1] = tmp2;
            _paths[index2] = tmp1;

            return _paths;
        }

    }
}
